package datastructure.linked;

/**
 * @Description: 环形链表定义
 * @author: Yang Qiang
 * @create: 2021-11-23 22:27
 */
public class CircleLinkedList<E> {
    private Node head = null; // 头节点
    private Node tail = null; // 尾节点

    /**
     * 约瑟夫问题解决(出圈的方法), 环形链表是事先定义好的
     * @param startNo: 从谁开始数, 也就是环形链表的头结点head
     * @param countNo: 数到第几个出圈
     * @param nums: 猴子的个数
     */
    public void exitCircle(int startNo, int countNo, int nums){
        // 边界的考量
        if (head == null || startNo > nums || startNo < 1){
            throw new RuntimeException("参数错误");
        }

        // 找准头指针和尾指针(也就是startNo等于几, 几就是头指针, 然后startNo的上一个就是尾指针)
        // 这里的时候已经初始化出来了有nums节点的环形链表
        for (int i = 0; i < startNo-1; i++) {
            // 循环一次就移动一次头尾节点
            head = head.next;
            tail = tail.next;
        }

        // 循环数数出圈
        while (true){
            // 头节点等于尾节点就是结束
            if (head == tail){
                break;
            }

            // 循环countNo次, 就是谁出圈
            // 比如数2个出圈, 这里就是数2个, 然后数完了后, 头节点就是需要出对的元素
            for (int i = 0; i < countNo-1; i++) {
                head = head.next;
                tail = tail.next;
            }
            System.out.println(head.e + "元素出圈");

            // 修正环形链表的头尾节点, 也就是这一步元素出圈了
            head = head.next;
            tail.next = head;
        }
    }


    /**
     * 构造函数->构造出来一个环形链表->尾插法
     * @param nums: 环形链表的节点个数
     */
    public CircleLinkedList(int nums) {
        if (nums < 1){
            throw new RuntimeException("数据错误");
        }
        for (int i = 1; i <= nums; i++) {
            // 循环声明一个节点
            Node node = new Node(i);
            if (i == 1){// 如果只有一个节点的话或者是第一个节点
                // 第一个节点等于头结点
                head = node;
                // 头结点的下一个节点等于头结点
                head.next = head;
                // 最后一个节点也等于头结点
                tail = node;
            }else {// 如果不是第一个节点的话
                // 尾节下一个节点等于新节点
                tail.next = node;
                // 新节点的下一个节点等于头节点
                node.next = head;
                // 新节点等于头节点
                tail = node;
            }
        }
    }

    // 无参构造
    public CircleLinkedList() {
        this(5);
    }
    /**
     * 定义节点Node对象
     */
    public class Node<E> {
        // 数据域
        public E e;
        // 指针域
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node() {
            this.e = null;
            this.next = null;
        }

        public Node(E e) {
            this.e = e;
            this.next = null;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }
}
